#include "..\CookHeader.h"

typedef struct _TreeNode {
	struct _TreeNode* left = NULL;
	string data;
	struct _TreeNode* right = NULL;
} TreeNode;

Array <TreeNode*> memory;
TreeNode* root;    // Ʈ  ()
Array <string> nameAry = { "ũ", "座", "", "ũ", "ɽ", "Ʈ̽" };

void freeMemory() {
	for (int i = 0; i < len(memory); i++)
		delete memory[i];
}

int main() {
	TreeNode* node;
	TreeNode* current; //   ۾ ()

	node = new TreeNode;
	node->data = nameAry[0];
	root = node;
	memory.push_back(node);

	for (int i = 1; i < len(nameAry); i++) {
		string name = nameAry[i];
		node = new TreeNode;
		node->data = name;

		current = root;
		while (true) {
			if (name < current->data) {
				if (current->left == NULL) {
					current->left = node;
					break;
				}
				current = current->left;
			}
			else {
				if (current->right == NULL) {
					current->right = node;
					break;
				}
				current = current->right;
			}
		}
		memory.push_back(node);
	}

	string deleteName = "";
	TreeNode* parent;  //   θ  ۾ ()

	current = root;
	parent = NULL;
	while (true) {
		if (deleteName == current->data) {
			if (current->left == NULL && current->right == NULL) {
				if (parent->left == current)
					parent->left = NULL;
				else
					parent->right = NULL;
				current->data = "None";
			}
			else if (current->left != NULL && current->right == NULL) {
				if (parent->left == current)
					parent->left = current->left;
				else
					parent->right = current->left;
				current->data = "None";
			}
			else if (current->left == NULL && current->right != NULL) {
				if (parent->left == current)
					parent->left = current->right;
				else
					parent->right = current->right;
				current->data = "None";
			}
			println(deleteName + " .");
			break;
		}
		else if (deleteName < current->data) {
			if (current->left == NULL) {
				println(deleteName + " Ʈ ");
				break;
			}
			parent = current;
			current = current->left;
		}
		else {
			if (current->right == NULL) {
				print(deleteName + " Ʈ ");
				break;
			}
			parent = current;
			current = current->right;
		}
	}
	freeMemory();
}